1. Field of the Invention
The present invention is related to computer graphics hardware for which OPENGL (GRAPHICS LIBRARY) software is an interface thereto, and, in particular, to accelerating minified texture cache access of the computer graphics hardware.
2. Description of the Related Art
Interactive graphics display, in general, is explained in Computer Graphics: Principles and Practices, Foley, vanDam, Feiner, and Hughes, Addison-Wesley, 1992, and in Principles of Interactive Computer Graphics, William M. Newman and Robert F. Sproull, Second Edition, McGraw-Hill Book Company, New York, 1979. Interactive graphics display generally includes a frame buffer storing pixels (or picture elements), a display, and a display controller that transmits the contents of the frame buffer to the display.
The OpenGL graphics system is a software interface to graphics hardware, and is explained in the OpenGL Programming Guide, The Official Guide to Learning OpenGL, Second Edition, Release 1.1, by the OpenGL Architecture Review Board, Jackie Neider, Tom Davis, Mason Woo, Addison-Wesley Developers Press, Reading, Massachusetts, 1997, in the OpenGL Programming Guide, The Official Guide to Learning OpenGL, Release 1, by the OpenGL Architecture Review Board, Jackie Neider, Tom Davis, Mason Woo, Addison-Wesley Publishing Company, Reading, Massachusetts, 1993, and in the OpenGL Reference Manual, The Official Reference Document for OpenGL, Release 1, the OpenGl Architecture Review Board, Addison-Wesley Publishing Company, Reading, Massachusetts, 1993.
A computer model for interpretation of OpenGL commands is a client-server model. An application program being executed by one computer, typically the client computer, issues commands, which are interpreted and processed by another computer, typically the server computer, on which OpenGL is implemented. The client may or may not operate on the same computer as the server. A computer, then, can make calls through an OpenGL software interface to graphics hardware, and the graphics hardware can reside either on the same computer making the calls or on a remote computer.
A tool for describing how data is processed in OpenGL is a processing pipeline. The OpenGL processing pipeline 10 shown in FIG. 1 receives commands, and may store the commands for future processing in a display list 14 or execute the commands immediately. The OpenGL processing pipeline includes an evaluator 16, which approximates curve and surface geometry by evaluating polynomial commands of the input values; per-vertex operations and primitive assembly 18, in which geometric primitives such as points, line segments, and polygons, described by vertices, are processed, such as transforming and lighting the vertices, and clipping the primitives into a viewing volume; rasterization 20 produces a series of frame buffer addresses and associated values, and converts a projected point, line, or polygon, or the pixels of a bitmap or image, to fragments, each corresponding to a pixel in the framebuffer; per-fragment operations 22 performs operations such as conditional updates to the frame buffer 24 based on incoming and previously stored depth values (to effect depth buffering) and blending of incoming pixel colors with stored colors, masking, and other logical operations on pixel values. The final pixel values are then stored in the frame buffer 24.
Pixel operations 26 processes input data from the commands 12 which is in the form of pixels rather than vertices. The result of the pixel operations 26 is stored in texture memory 28, for use in rasterization 20. The resulting fragments are merged into the frame buffer 24 as if the fragments were generated from geometric data.
In addition, if texturing is enabled during rasterization 20, a texel is generated from texture memory 28 for each fragment and applied to the fragment. A texel is a texture element obtained from texture memory and represents the color of the texture to be applied to a corresponding fragment. Texturing maps a portion of a specified texture image onto each primitive. Texture mapping is accomplished by using the color (Red (R), Green (G), Blue (B), or Alpha (A)) of the texture image at the location indicated by the fragment's (s, t, and r) coordinates. In the case of a 2-dimensional image (2-D image), s and t coordinates are applicable, and in the case of a 3-dimensional image (3-D image), then s, t, and r coordinates are applicable.
OpenGL provides a way to specify the details of how texturing of a primitive is effected. These details include specification of the image to be texture mapped, the means by which the image is filtered when applied to the primitive, and the function that determines what RGBA value is produced given a fragment color and an image value. A command specifying the target, level, internal format, width, height, border, format, type, and *data (a pointer to the data) is used to specify the texture image in GI, commands such as TexImage2D or TexImage1D. The level argument is an integer level-of-detail number. The main texture image has a level of detail number of 0, and if a level of detail less than 0 is specified, an error message is generated.
The maximum allowable width or height of the image is an implementation dependent function of the level of detail and internal format of the resulting image array. An image with zero height or width indicates the null texture. If the null texture is specified for level of detail zero, it is as if texturing were disabled.
The image indicated to the GL (or graphics library) by the image pointer is decoded and copied into the GL's internal memory. This copying effectively places the decoded image inside a border of the maximum allowable width, which is currently 1, whether or not a border has been specified.
An example of a texture image 29 and the coordinates used to access it is shown in FIG. 2. FIG. 2 shows a two-dimensional texture image with n.times.m dimensions of n=3 and m=2. A one-dimensional texture would comprise a single strip. The values, .alpha. and .beta., used in blending adjacent texels to obtain a texture value are also shown. As shown in FIG. 2, values of s and t coordinates are each in the range of 0.0 to 1.0.
If no border or a border smaller than the maximum allowable width has been specified, then the image is still stored as if it were surrounded by a border of the maximum possible width. Any excess border (which surrounds the specified image, including any border) is assigned unspecified values. A one-dimensional texture has a border only at its left and right ends.
The decoded image is referred to as the texture array. A two-dimensional texture array has width w.sub.t =2.sup.n +2b.sub.t and height h.sub.t =2.sup.m +2b.sub.t, where b.sub.t is the maximum allowable border width; and a one-dimensional texture array has width w.sub.t =2.sup.n +2b.sub.t and height h.sub.t =1.
Texturing, including determination of the level of detail and selection of a mipmap, of the related art is now discussed, with reference being made to OpenGL commands using the OpenGL command syntax.
Object coordinates (x, y, z, and w) and texture coordinates (s, t, r, and q) are provided for each vertex.
A texel is an element (i,j) of the texture array (for a 1-dimensional array, j is irrelevant). The texture value used in texturing a fragment is determined by that fragment's associated (s,t) coordinates, but as shown in FIG. 2 may not correspond to any actual texel.
Typically, there are 8 neighboring texels for each pixel, which means that 8 texels encompass or surround each pixel.
Texture images may also be specified using image data taken directly from the framebuffer, and rectangular subregions of existing texture images may be respecified.
If texture wrapping for the s or t coordinates is set to be repeated (by setting parameters such as TEXTURE.sup.-- WRAP.sup.-- S or TEXTURE.sup.-- WRAP.sup.-- T to REPEAT), then the GL ignores the integer part of the s or t coordinates, respectively, using only the fractional part. For a number r, the fractional part is r-.left brkt-bot.r.right brkt-bot., regardless of the sign of r, and the floor function truncates towards -.infin.. The parameter CLAMP causes s or t coordinates to be clamped to the range [0,1]. The initial state is for both s and t behavior to be that given by the repeat value.
Applying a texture to a primitive implies a mapping from texture image space to framebuffer image space. In general, this mapping involves a reconstruction of the sampled texture image, followed by a projective warping implied by the mapping to framebuffer space, then a filtering, followed finally by a resampling of the filtered, warped, reconstructed image before applying it to a fragment.
In the GL, this mapping is approximated by one of two simple filtering schemes. One of these schemes is selected based on whether the mapping from texture space to framebuffer space is deemed to magnify or minify the texture image. The choice is governed by a scale factor .rho.(x,y) and .lambda.(x,y) .XI.log.sub.2 [.rho.(x,y)]; if .lambda.(x,y) is less than or equal to a constant (the selection of the constant is described herein below) the texture is said to be magnified; if it is greater, the texture is minified. .lambda. is referred to as the level of detail.
Let s(x,y) be the function that associates an s texture coordinate with each set of window coordinates (x,y) that lie within a primitive, and t(x,y) be defined analogously. Let u(x,y)=2.sup.n S(x,y) and v(x,y)=2.sup.m t(x,y) (for a one-dimensional texture, define v(x,y).XI.0). For a polygon, .rho. is given at a fragment with window coordinates (x,y) by ##EQU1## where .differential.u/.differential.x indicates the derivative of u with respect to window x, and similarly for the other derivatives. Equation (1) is rotationally invariant, which means that if the image is rotated around, the same level of detail is provided. However, equation (1) is very compute-intensive.
For a line, the formula is ##EQU2## where .DELTA.x=x.sub.2 -x.sub.1 and .DELTA.y=Y.sub.2 -Y.sub.1 with (x.sub.1,y.sub.1) and (x.sub.2,y.sub.2) being the segment's window coordinate endpoints and 1=.sqroot..DELTA.x.sup.2 +.DELTA.y.sup.2 . For a point, pixel rectangle, or bitmap, .rho..uparw.1.
While equations (1) and (2) give the best results when texturing, they are often impractical to implement. Therefore, an implementation may approximate the ideal .rho. with a function f(x,y) subject to these conditions:
1. f(x,y) is continuous and monotonically increasing in each of .vertline..differential.u/.differential.y.vertline.,.vertline..differentia l.v/.differential.x.vertline., and .vertline..differential.v/.differential.y.vertline., PA1 2. Let ##EQU3##
Then max {m.sub.u,m.sub.v }.ltoreq.f (x,y).ltoreq.m.sub.u +m.sub.u. Max{m.sub.u,m.sub.v } is the rectangular level of detail calculation, and m.sub.u +m.sub.v is the fuzziest permissible limit, but is very fuzzy.
When .lambda. indicates minification, the value assigned to the TEXTURE.sub.-- MIN.sub.-- FILTER parameter is used to determine how the texture value for a fragment is selected. When TEXTURE.sub.-- MIN.sub.-- FILTER is NEAREST, the texel nearest (in Manhattan distance) to that specified by (s,t) is obtained. This means the texel at location (i,j) becomes the texture value, with i given by ##EQU4##
If TEXTURE.sup.-- WRAP.sup.-- S is REPEAT, then 0.ltoreq.s &lt;1.
Similarly, j is found as ##EQU5##
For a one-dimensional texture, j is irrelevant; the texel at location i becomes the texture value.
When TEXTURE.sub.-- MIN.sub.-- FILTER is LINEAR a 2.times.2 square of texels is selected. This square is obtained by first computing ##EQU6## and ##EQU7## Then ##EQU8## and ##EQU9## Let EQU .alpha.=frac(u-1/2) and .beta.=frac(v-1/2)
where frac(x) denotes the fractional part of x. Let T.sub.ij be the texel at location (i,j) in the texture image. Then the texture value, .tau. is found as EQU .tau.=(1-.alpha.)(1-.beta.).tau..sub.iojo +.alpha.(1-.beta.).tau..sub.iojo +(1-.alpha.).beta..tau..sub.iojo +.alpha..beta..tau..sub.ij (5)
for a two-dimensional texture.
For a one-dimensional texture, EQU .tau.=(1-.alpha.).tau..sub.io +.alpha..tau..sub.i1 (6)
where .tau..sub.i indicates the texel at location i in the one-dimensional texture. If any of the selected .tau..sub.ij (or .tau..sub.i) in the above equations refer to a border texel with i&lt;-b.sub.s, j&lt;-b.sub.s, i.gtoreq.w.sub.s -b.sub.s, or j.gtoreq.h.sub.s -b.sub.s, then the border color given by the current setting of the parameter TEXTURE.sub.-- BORDER.sub.-- COLOR is used instead of the unspecified value or values.
The RGBA values of the TEXTURE.sub.-- BORDER.sub.-- COLOR are interpreted to match the texture's internal format in a manner consistent with Table 1.
TABLE 1 ______________________________________ Base Internal RGBA Texture Format Values Components ______________________________________ ALPHA A A LUMINANCE R L LUMINANCE ALPHA R,A L,A INTENSITY R I RGB R,G,B R,G,B RGBA R,G,B,A R,G,B,A ______________________________________
OpenGL parameters of TEXTURE.sub.-- MIN.sub.-- FILTER, including NEAREST.sub.-- MIPMAP.sup.-- NEAREST, NEAREST.sub.-- MIPMAP.sup.-- LINEAR, LINEAR.sub.-- MIPMAP.sup.-- NEAREST, and LINEAR.sub.-- MIPMAP.sup.-- LINEAR, each require the use of a mipmap. A mipmap is an ordered set of arrays representing the same image; each array has a resolution lower than the previous one. If the texture has dimensions 2.sup.n .times.2.sup.m, then there are max{n,m}+1 mipmap arrays. The first array is the original texture with dimensions 2.sup.n .times.2.sup.m. Each subsequent array has dimensions 2.sup.(k-1) .times.2.sup.(l-1) where 2.sup.k .times.2.sup.l are the dimensions of the previous array. This is the case as long as both k&gt;0 and 1&gt;0. Once either k=0 or l=0, each subsequent array has dimension 1.times.2.sup.(l-1) or 2.sup.(k-1) .times.1, respectively, until the last array is reached with dimension 1.times.1.
Each array in a mipmap is transmitted to the GL using TexImage2D or TexImage1D; the array being set is indicated with the level-of-detail argument. Level-of-detail numbers proceed from 0 for the original texture array through p=max{n,m} with each unit increase indicating an array of half the dimensions of the previous one as already described. If texturing is enabled (and TEXTURE.sub.-- MIN.sub.-- FILTER is one that requires a mipmap) at the time a primitive is rasterized and if the set of arrays 0 through p is incomplete, based on the dimensions of array 0, then it is as if texture mapping were disabled. The set of arrays 0 through p is incomplete if the internal formats of all the mipmap arrays were not specified with the same symbolic constant, or if the border widths of the mipmap arrays are not the same, or if the dimensions of the mipmap arrays do not follow the sequence described above. Arrays indexed greater than p are insignificant.
The mipmap is used in conjunction with the level of detail to approximate the application of an appropriately filtered texture to a fragment.
Let p=max{n,m} and let c be the value of .lambda. at which the transition from minification to magnification occurs, and, for minification, values of .lambda. where .lambda.&gt;c are applicable. For the NEAREST.sub.-- MIPMAP.sup.-- NEAREST parameter, if c&lt;.lambda..ltoreq.0.5 then the mipmap array with level-of-detail of 0 is selected. Otherwise, the dth mipmap array is selected when d-1/2&lt;.lambda..ltoreq.d+1/2 as long as 1.ltoreq.d .ltoreq.p. If .lambda.&gt;p+1/2, then the pth mipmap array is selected. The rules for NEAREST are then applied to the selected array.
The same mipmap array selection rules apply for LINEAR.sub.-- MIPMAP.sup.-- NEAREST as for NEAREST.sub.-- MIPMAP.sup.-- NEAREST, but the rules for LINEAR are applied to the selected array.
For NEAREST.sub.-- MIPMAP.sup.-- LINEAR, the level d-1 and the level d mipmap arrays are selected, where d-1.ltoreq..lambda.&lt;d, unless .lambda..gtoreq.p, in which case the pth mipmap array is used for both arrays. The rules for NEAREST are then applied to each of these arrays, yielding two corresponding texture values .tau..sub.d-1, and .tau..sub.d. The final texture value is then found as EQU .tau.=[1-frac(.lambda.)].tau..sub.d-1 +frac(.lambda.).tau..sub.d.(7)
LINEAR.sub.-- MIPMAP.sup.-- LINEAR has the same effect as LINEAR.sub.-- MIPMAP.sup.-- LINEAR except that the rules for LINEAR are applied for each of the two mipmap arrays to generate .tau..sub.d-l and .tau..sub.d.
Texture magnification is now explained. When .lambda. indicates magnification, the value assigned to TEXTURE.sub.-- MAG.sub.-- FILTER determines how the texture value is obtained. There are two possible values for TEXTURE.sub.-- MAG.sub.-- FILTER: NEAREST and LINEAR. NEAREST behaves exactly as NEAREST for TEXTURE.sub.-- MIN.sub.-- FILTER (equation (3) and (4) are used); LINEAR behaves exactly as LINEAR for TEXTURE.sub.-- MIN.sub.-- FILTER (equation (5) is used). The level-of-detail 0 texture array is always used for magnification.
In addition, there is a choice of c, the minification vs. magnification switch-over point. If the magnification filter is given by LINEAR and the minification filter is given by NEARES.tau..sub.-- MIPMAP.sup.-- NEAREST or NEARES.tau..sub.-- MIPMAP.sup.-- LINEAR, then c=0.5. This is done to ensure that a minified texture does not appear "sharper" than a magnified texture. Otherwise, c=0.
Multiple levels of detail in OpenGL allow textured objects to be viewed at different distances from a viewpoint by determining which of the mipmap images in a pyramid of mipmaps of the same image to select, and by filtering between 2 levels of detail to minimize aliasing artifacts.
Mipmapping prevents aliasing in texel space and eliminates aliasing artifacts by blurring between levels of detail, one of which is not aliasing and the other of which is slightly aliasing. For example, a brick wall would appear as noise without aliasing if a full resolution image of the brick wall were to be applied to a brick wall that is far enough from the viewer to appear as a single pixel.
The texture coordinates determine what part of the texture in the texture map is assigned to that vertex, with texture coordinates being linearly interpolated between vertices. Texture coordinates include one, two, three, or four coordinates, and are usually referred to as the s, t, r, and q coordinates.
An image can be magnified (enlarged) or minified (reduced in size), and texturing associated with the magnification or minification must be appropriately scaled.
In the related art, for each pixel, the texturing such as the s and t coordinates and the level of detail associated with each pixel must be analyzed to determine the appropriate texturing for the image being scaled and displayed.
Also in the related art, techniques for magnifying and minifying images are implemented as follows. For magnification of images, the texture coordinates are stepped through slowly, without mipmapping, and using bilinear interpolation techniques. For minification of images, a detail texture is to be displayed, and mipmapping is required to prevent aliasing and to limit the size of the footprint of pixels in texture space stored in the texture memory. Therefore, in the related art, trilinear interpolation, involving the s and t coordinates and the level of detail, is required for mipmapping. To avoid aliasing during minification, proper sampling of the texture is required, and, typically, a prefiltered coarse representation of the image is selected and displayed, with smooth interpolation between levels of detail to prevent popping.
Mipmapping can be turned off. However, in some computers available from Silicon Graphics, Inc., a performance penalty is imposed given the architecture thereof.
In particular, if an image is heavily minified, then the texture stored in the texture cache is stepped through at hundreds of texels per pixel or more, fetching an entire tile of texels from the texture memory into the texture cache, but using only a small percentage of that tile is actually used, potentially thrashing the texture cache. The foregoing procedure may result in a performance hit ratio of 100 to 1.
A problem in the related art is that textures in extreme minification are highly non-local, which reduces texture cache performance, degrading texture cache performance by as much as two orders of magnitude.